\chapter{Étude}

Nous avons choisi d'implémenter les algorithmes proposés en python, en nous appuyant sur l'API Python de Tulip\cite{tulip}.

\section{Distance d'édition sous contrainte de Zhang}

La méthode décrite par Zhang dans \cite{zhang96} permet de calculer une distance d'édition propre pour chaque paire de nœuds issus des deux arbres non ordonnés sur lesquels nous travaillons. Zhang propose une distance d'édition sous-contrainte, reprenant la définition initiale de la distance d'édition et en rajoutant la contrainte qu'il énonce ainsi : deux sous-arbres disjoints ne peuvent être mis en correspondance qu'avec deux arbres eux même disjoints (conservation de l'ancêtre commun).  Ainsi, il réduit l'espace de recherche de manière à ramener le problème à un problème de classe polynomiale.  \\

\subsection{L'algorithme}\label{algoZhang}
Il s'agit de parcourir nos deux arbres, de constituer toutes les paires de nœuds possibles et de calculer la distance d'édition d'un nœud par rapport à l'autre. de manière a obtenir une matrice d'alignement.\\

Il est nécessaire avant toute chose de fixer les coûts des opérations d'insertion, de suppression et de permutation qui nous permettrons par la suite d'estimer les distances d'édition entre nœuds.\\
Zhang considère que les opérations d'insertion et de suppression sont de même coût. Il propose une description récursive du calcul de la distance d'édition.\\

La distance d'édition entre un arbre donné et un arbre vide (noté D(T)) est égale a la somme de la distance d'éditions entre la sous-forêt issue de l'arbre en question et un arbre vide, et du coût de l'opération d'insertion / suppression.\\

La distance d'édition entre une forêt et un arbre vide (noté D(F)) correspond à la somme des distances d'éditions des arbres de cette forêt.\\

La distance d'édition entre deux forêts (noté D(F1,F2)) est égale à la distance minimum entre :\\

\begin{itemize}
\renewcommand{\labelitemi}{$\circ$}
\item la somme de D(F2) et du minimum entre les distances d'éditions entre F1 et les sous forets de F2 moins la distance d'édition de la sous foret de F2 courante
\item la somme de D(F1) et du minimum entre les distances d'éditions entre les sous forets de F1 et F2 moins la distance d'édition de la sous foret de F1 courante
\item le coût du parcours de flot maximum/coût minimum à partir d'un graphe de flot construit à partir des arbres de F1 et F2 (fig. \ref{zhangflow}). En effet, Zhang réduit le problème de recherche de la mise en correspondance optimale de deux forêts au problème de la recherche du parcours de flot maximum/coût minimum  (\textit{Minimum Cost Maximum Flow}).
\\
\end{itemize}

La distance d'édition entre deux arbres (noté D(T1,T2) ) va donc pouvoir être calculé en trouvant le minimum entre :\\
\begin{itemize}
\renewcommand{\labelitemi}{$\circ$}
\item la somme de D(T1) et du minimum entre les distances d'éditions entre T1 et les sous arbres de T2 moins la distance d'édition D(sous-arbre de T2 courant)
\item la somme de D(T2) et du minimum entre les distances d'éditions entre les sous arbres de T1 et T2 moins la distance d'édition D(sous-arbre de T1 courant)
\item la somme de D(F1, F2) (avec F1 et F2 respectivement les sous forets de T1 et T2) moins le coût de permutation fixé auparavant
\\
\end{itemize}
La matrice qui en résulte va permettre de trouver des correspondances entre nos deux arbres et de les aligner tout en conservant les plus petits ancêtres communs.\\

\subsection{Tulip}
Les notions d'arbre ou de forêts ne sont pas présentes dans Tulip, qui se veut être un logiciel de visualisation et d'analyse de graphes plus généraliste. Il nous faut donc reconsidérer les opérations décrites dans la partie \ref{algoZhang}.\\
Un arbre va se résumer en un nœud racine auquel seront rattachés un ensemble de nœuds par des arêtes. Chaque arête sera orienté pour aller de la racine vers les feuilles.
Ainsi pour connaître l'ensemble des nœuds qui descendent au premier degré de N (un nœud quelconque dans un arbre) il nous suffira d'appeler la fonction \textit{tlp.graph.getOutNodes(N)} qui nous fournira un itérateur sur l'ensemble des nœuds souhaité.

\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.6]{res/zhangDTtulip.png}
\caption{\it Méthode pour le calcul de la distance d'édition D(T) en Python avec Tulip}
\label{tdtulip}
\end{center}
\end{figure}
\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.6]{res/zhangDFtulip.png}
\caption{\it Méthode pour le calcul de la distance d'édition D(F) en Python avec Tulip}
\label{tftulip}
\end{center}
\end{figure}

\pagebreak
\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.4]{res/dist1.png}
\caption{\it Les trois opérations d'édition (d'après \cite{theseouangraoua})}
\label{operationEdition}
\end{center}
\end{figure}

\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.8]{res/sousforet.png}
\caption{\it La sous-forêt de N correspond à l'ensemble des sous arbres issues de N}
\label{sousForet}
\end{center}
\end{figure}
%

\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.4]{res/zhangflow.png}
\caption{\it Graphe de flux construit a partir des arbres des sous forets de i et j. Pour chaque arête, on associe un coût de passage et une capacité maximum (d'après \cite{zhang96})}
\label{zhangflow}
\end{center}
\end{figure}
\pagebreak

\section{Modèle multi-échelle}

L'implémentation d'un modèle multi-échelles nécessite la détermination de la granularité présentée à chaque échelle et du nombre d'échelles de détails voulus (fig. 2.1). Rappelons que nous n'étudions ici que la représentation multi-échelles des détails d'une plante dans un état donné, à un instant fixé (\textit{snapshot}).
\\
\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.3]{res/arbre-multi-echelles.png}
\caption{\it Représentation d'une plante à trois échelles différentes : (a) échelle des axes , (b) échelle des unités de croissances, (c) échelle des entre-noeuds (d'après \cite{theseferraro})}
\end{center}
\end{figure}
\\
Deux échelles consécutives sont liées par une mise en correspondance de leurs sommets (fig 2.2). L'utilisation d'une structure récursive peut décrire une telle relation. Tulip met à notre disposition une structure adaptée à cette approche : les meta-noeuds, un noeud contenant un sous-graphe.
\begin{figure}[ht]
\begin{center}
\includegraphics[scale=0.6]{res/general-multi-scale.png}
\caption{\it Mise en correspondance des sommets d'échelles consécutives (d'après \cite{godin98})}
\end{center}
\end{figure}
\pagebreak

Quelle que soit la granularité choisie, la construction d'un MTG à partir d'un arbre enraciné mono-échelle suit la même logique. Notre point de départ est le chargement de la description d'une arborescence dans le format Tulip (extension \textit{tlp}). 

\subsection{Prérequis}
Notre tentative de description d'un algorithme général permettant de mettre en œuvre une représentation multi-échelles à partir d'une arborescence s'est en premier lieu confronter à la définition d'un cadre initial.\\

\begin{itemize}
\renewcommand{\labelitemi}{$\circ$}
\item les sommets ont 1 type
\item les types ont une relation d'ordre
\item 1 niveau correspond à 1 ou n type
\item 1 type n'est associé qu'à 1 seul niveau
%\item les types associés à 1 même niveau ont une relation d'ordre directe
\end{itemize}

\subsection{Adaptation Tulip}
Tulip permet d'associer un sommet à une ou plusieurs valeurs pouvant servir à intégrer la notion de typage. La hiérarchie de ces types, et l'association des types à un niveau donné peuvent dans un premier temps être définis en statique dans le code.

%\subsubsection{Principe}

\subsection{Sérialisation}
Le format de fichier Tulip permet de décrire des groupements de sommets et arêtes sous la notion de cluster. Cette abstraction pourrait facilement permettre l'export/import de modèles multi-échelles.
